﻿//#include<stdio.h>
//#include<string>
//#include<stdlib.h>
//#include<windows.h>//系统工具库
//#include<iostream>
//#include<iomanip>
//#include<fstream>
//
//using namespace std;
//
//#define OK 1
//#define ERROR 0
//#define OVERFLOW -1
//#define MAXSIZE 100
//
//typedef char AT;//值类型重定义
//
//int _size;//全局变量计数
//
//typedef struct BT
//{
//	AT data;//数据域
//	BT* left;//左
//	BT* right;//右
//};
//
//
//void BTInit(BT* B)
//{
//
//}
//
//
//
//
//
//
//
////借助队列实现广义遍历******************************************************************
//typedef BT* ET;
//
//typedef struct  sq//重定义结构体名为sq
//{
//	ET* data;//数据的基地址
//	int front;//头指针
//	int rear;//尾指针
//};
//int InitSq(sq* Q)//初始化
//{
//	Q->data = NULL;//初始化为空
//	Q->data = (ET*)realloc(Q->data, MAXSIZE * sizeof(ET));//realloc开辟100个ET类型的空间
//	Q->front = Q->rear = 0;//头尾指针置空
//	if (Q->data == NULL)//如果申请失败则退出
//	{
//		cout << "内存申请失败！" << endl;
//		exit(OVERFLOW);
//	}
//	return OK;
//}
//int SqDestroy(sq* Q)//销毁队列
//{
//	if (Q->data == NULL)//若data地址已经为空则直接退出
//	{
//		return OVERFLOW;
//	}
//
//	free(Q->data);//释放data
//	Q->data = NULL;
//	Q->front = Q->rear = 0;
//	return OK;
//}
//int SqPush(sq* Q, ET x)//入队
//{
//	if (((Q->rear) + 1) % MAXSIZE == Q->front)
//	{
//		return OVERFLOW;
//	}
//
//	Q->data[Q->rear] = x;//x入队尾
//	Q->rear = ((Q->rear) + 1) % MAXSIZE;//队尾指向队尾的下一个
//	return OK;
//}
//
//ET SqPop(sq* Q)//出队
//{
//	if ((Q->front) == (Q->rear))
//	{
//		printf("队空！\n");
//	}
//
//	ET e;
//	e = Q->data[Q->front];
//	Q->front = ((Q->front) + 1) % MAXSIZE;
//	return e;
//}
//
//ET SqFront(sq* Q)
//{
//	if (Q->data != NULL)
//		return Q->data[Q->front];
//}
//
////***********************************************************************
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
////遍历类--深度优先
//int popbt1(BT* B)//先序遍历
//{
//	if (B == NULL)
//	{
//		printf("NULL ");
//		return 0;
//	}
//
//	printf("%c ", B->data);
//	popbt1(B->left);
//	popbt1(B->right);
//}
//
//int popbt2(BT* B)//中序遍历
//{
//	if (B == NULL)
//	{
//		printf("NULL ");
//		return 0;
//	}
//
//	popbt2(B->left);
//	printf("%c ", B->data);
//	popbt2(B->right);
//}
//
//int popbt3(BT* B)//后序遍历
//{
//	if (B == NULL)
//	{
//		printf("NULL ");
//		return 0;
//	}
//
//	popbt3(B->left);
//	popbt3(B->right);
//	printf("%c ", B->data);
//}
//
//
//
//
//
//
//
//
//
////节点数计算类
//void TSize(BT* B) //计算节点数-全局变量计数法-C++重载
//{
//	if (B == NULL)
//	{
//		return;
//	}
//	else
//	{
//		++_size;
//	}
//	TSize(B->left);
//	TSize(B->right);
//}
//
//
//void TSize(BT* B,int* size)//计算节点数-指针自加传值遍历法-C++重载
//{
//	if (B == NULL)
//	{
//		return;
//	}
//	else
//	{
//		++(* size);
//	}
//	TSize(B->left,size);
//	TSize(B->right,size);
//}
//
//int TSizes(BT* B)//计算节点数-后序遍历法
//{
//	return B == NULL ? 0 : TSizes(B->left) + TSizes(B->right) + 1;//左子树+右子树+根节点(或节点的左右节点数+自己)
//}
//
//
//int TSizesLeaf(BT* B)//计算叶子节点数-后序遍历法
//{
//	if (B == NULL)//如果树为空则返回0
//	{
//		return 0;
//	}
//	else if (B->left == NULL && B->right == NULL)//如果为叶子节点则返回1
//	{
//		return 1;
//	}
//	return TSizesLeaf(B->left)+ TSizesLeaf(B->right);//返回左子树的所有叶子节点加上右子树的所有叶子节点(第二层次开始算)
//}
//
//
//
//
////层序遍历--广度优先
////核心思路：出队时按从左到右存入下一层的节点
//void Popat(BT*B)//队列实现层序遍历--先根后左后右
//{
//	sq Q;
//	InitSq(&Q);//初始化
//	if (B)//树不为空则入队
//	{
//		SqPush(&Q, B);
//	}
//
//	while (Q.front != Q.rear)//如果队不为空
//	{
//		BT* nc = SqFront(&Q);//取头元素
//		SqPop(&Q);//出队(弹出头元素)
//		printf("%c ",nc->data);
//		if (nc->left)//左节点不为空
//		{
//			SqPush(&Q, nc->left);//左节点入队
//		}
//		if (nc->right)//右节点不为空
//		{
//			SqPush(&Q, nc->right);//右节点入队
//		}
//	}
//	SqDestroy(&Q);//销毁队列
//}
//
//
//
//
//int main()
//{
//	
//}

//            A
//      B           C
//   D     E